﻿
#include<iostream>
using namespace std;

#include<stack>
#include<queue>
//最小栈
//支持push pop top操作，并且能在常数实际内检索到最小元素的栈
//思路1：用一个变量min去记录最小元素，入的值比min小，就改变min，比min大则min值不更新
//上述思路不行，因为如果有删除操作，min被删掉，也就无法根据入的值来判断min和入的值的大小
//
// 优化;
//思路2：用双栈来解决：st 和 minst
//minst 只有在st中有更小的值的时候才存数据
//-------------------------->栈顶
//st：    3  4  2  6  2  0
//minst： 3  1  0
//1，当st删除的是0的时候，对应的minst中的0也要删除
//2，st删除的是2，minst中没有2，那么就不删除，最小值还是栈顶的1（0还没被删就是0）
//
// ***情况2***
// st：   3  4  1  6  入1
// minst：3  1  ？ 
// minst中？的位置要不要随着st中的新入的1来插入这个对应的1呢？
//答案是肯定的：如果和minst栈顶相同的新入最小值不插入，那么只剩同一个最小值，当新入的值被删掉时，该有的最小值就没有了
//所以：minst应该更新为：3  1  1

class MinStack{
public:
	MinStack()
	{

	}
	//里面不写初始化，他也会走初始化列表

	void push(int val)
	{
		_st.push(val);
		if (_minst.empty() || val <= _minst.top())
		{
			_minst.push(val);
		}
	}

	void pop()
	{
		if (_minst.top() == _st.top)
		{
			_minst.pop();
		}
		_st.pop(); 
	}

	int top()
	{
		return _st.top();
	}

	int getMin()
	{
		return _minst.top();
	}


	stack<int> _st;
	stack<int> _minst;
};


//栈的压入，弹出序列
//第一个序列表示栈的压入序列，请判断第二个序列是否可能成为该栈的弹出顺序（压入栈的所有数字都不相同）
//入栈序列：12345
//出栈序列：43512❌
//出栈序列：54321✔

//用一个c栈来存储站内的元素
//入栈序列 12345
//出栈序列 45321
//1，入栈序列先入c栈一个值 
//2，栈顶元素和出栈序列比较：相等：出栈序列往后走，c栈顶元素出（相等匹配（出栈序列）成功出栈）
//                         不等：回到第一步，继续入（不等：继续入栈比较匹配）
// 
// 比较的结束条件：（入栈序列全部结束时）
// 1，相等匹配 出栈出完了or出栈序列走到尾（相当于入栈序列都被匹配完）：匹配成功
// 2，不匹配 栈不为空（还有没匹配成功的值）or出栈序列没走到尾：匹配失败
// 
class stack_match {
	bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
	{
		size_t popi = 0;
		stack<int> s;
		for (auto e : pushV)
		{
			s.push(e);

			//入一个匹配一次
			while (!s.empty() && s.top() == popV[popi])//能匹配，出栈序列往后走，这个匹配上的值出栈
			{
				++popi;
				s.pop();
			}
		}
		//pushV走完后
	    //看s是否为空
		return s.empty();
	}
};

//逆波兰表达式


//二叉树的层序遍历
class solution
{
public:
	vector<vector<int>> levelOrder(TreeNode* root)
	{
		vector<vector<int>> vv;
		if (root == nullptr)
		{
			return vv;//空树
		}




		//
		queue<TreeNode*> q;
		q.push(root);
		//用队列存根节点数据

		
		int levelSize = 1;

		while (!q.empty())
		{
			//出完的数据放到一个单层的缓冲区v
			vector<int> v;
			//每一层都出当前层的根，再把儿子放进去
			while (levelSize--)
			{

				//取头（根节点）
				TreeNode* front = q.front();//头节点保存
				q.pop();//再删除

				v.push_back(front->val);

				//取了根还要取左右孩子：下一层；
				//递归取出每一层：
				if (front->left)
					q.push(front->left);

				if (front->right)
					q.push(front->right);
				//？？？都存在q这个队列里，怎么实现存储在双层的数组里：区分取出的是哪一层，需要怎么用[]包起来
			}
			
			//优化：
			//用一个变量控制，一层一层的出队列
			//每层数据个数levelsize,来控制，一层一层地出队列
			//第一层是levelsize：1
			
			//把得到的【】第二层的元素存入vv
			vv.push_back(v);
			//当前层出完了，继续下一层
			levelSize = q.size();//更新层节点个数（当前这个队列没有被pop的元素个数）
		}
		return vv;
	}

};




















